class Solution {
    int memo[][];


    public int countDigitOne(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int m = s.length;
        memo = new int[m][1<<10];
        for(int i = 0;i<m;i++)
        {
            Arrays.fill(memo[i],-1);
        }
        return n - f(0,0,true,false,memo,s);

    }

    public int f(int i,int mask,boolean is_limit,boolean is_num,int[][] memo,char[] s)
    {
        if(i==s.length)
        {
            return is_num?1:0;
        }
        if(!is_limit&&is_num&&memo[i][mask]!=-1)
        {
            return memo[i][mask];
        }
        int res = 0;
        if(!is_num)
        {
            res = f(i+1,mask,false,false,memo,s);
        }
        int up = is_limit?s[i]-'0':9;
        for(int d = is_num?0:1;d<=up;d++)
        {
            if((mask>>d&1)==0)
            {
               res+=f(i+1,mask|(1<<d),is_limit&&d==up,true,memo,s);
            }
        }
        if(!is_limit&&is_num)
        {
           memo[i][mask]=res;
        }
        return res;
    }
}